package com.jack.leetcode.每日一题;

/*** 
 * @author zhangjie
 * @date 2020/4/24 22:57
 */
public class 数组中的逆序对 {

    int merge(int[] arr, int start, int end) {
        if (start >= end) {
            return 0;
        }
        int mid = (start + end) / 2;
        int count = merge(arr, start, mid) + merge(arr, mid + 1, end);
        int[] tmp = new int[end - start + 1];
        int i = start, j = mid + 1, k = 0;
        while (i <= mid && j <= end) {
            count += arr[i] <= arr[j] ? j - (mid + 1) : 0;
            tmp[k++] = arr[i] > arr[j] ? arr[j++] : arr[i++];
        }
        while (i <= mid) {
            count += j - (mid + 1);
            tmp[k++] = arr[i++];
        }
        while (j <= end) {
            tmp[k++] = arr[j++];
        }
        System.arraycopy(tmp, 0, arr, start, end - start + 1);
        return count;
    }
}
